// Copyright 2018 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_COMPILER_FUNCTIONAL_LIST_H_
#define V8_COMPILER_FUNCTIONAL_LIST_H_

#include "src/zone/zone.h"

namespace v8 {
namespace internal {
    namespace compiler {

        // A generic stack implemented as a purely functional singly-linked list, which
        // results in an O(1) copy operation. It is the equivalent of functional lists
        // in ML-like languages, with the only difference that it also caches the length
        // of the list in each node.
        // TODO(tebbi): Use this implementation also for RedundancyElimination.
        template <class A>
        class FunctionalList {
        private:
            struct Cons : ZoneObject {
                Cons(A top, Cons* rest)
                    : top(std::move(top))
                    , rest(rest)
                    , size(1 + (rest ? rest->size : 0))
                {
                }
                A const top;
                Cons* const rest;
                size_t const size;
            };

        public:
            FunctionalList()
                : elements_(nullptr)
            {
            }

            bool operator==(const FunctionalList<A>& other) const
            {
                if (Size() != other.Size())
                    return false;
                iterator it = begin();
                iterator other_it = other.begin();
                while (true) {
                    if (it == other_it)
                        return true;
                    if (*it != *other_it)
                        return false;
                    ++it;
                    ++other_it;
                }
            }
            bool operator!=(const FunctionalList<A>& other) const
            {
                return !(*this == other);
            }

            const A& Front() const
            {
                DCHECK_GT(Size(), 0);
                return elements_->top;
            }

            FunctionalList Rest() const
            {
                FunctionalList result = *this;
                result.DropFront();
                return result;
            }

            void DropFront()
            {
                CHECK_GT(Size(), 0);
                elements_ = elements_->rest;
            }

            void PushFront(A a, Zone* zone)
            {
                elements_ = new (zone) Cons(std::move(a), elements_);
            }

            // If {hint} happens to be exactly what we want to allocate, avoid allocation
            // by reusing {hint}.
            void PushFront(A a, Zone* zone, FunctionalList hint)
            {
                if (hint.Size() == Size() + 1 && hint.Front() == a && hint.Rest() == *this) {
                    *this = hint;
                } else {
                    PushFront(a, zone);
                }
            }

            // Drop elements until the current stack is equal to the tail shared with
            // {other}. The shared tail must not only be equal, but also refer to the
            // same memory.
            void ResetToCommonAncestor(FunctionalList other)
            {
                while (other.Size() > Size())
                    other.DropFront();
                while (other.Size() < Size())
                    DropFront();
                while (elements_ != other.elements_) {
                    DropFront();
                    other.DropFront();
                }
            }

            size_t Size() const { return elements_ ? elements_->size : 0; }

            class iterator {
            public:
                explicit iterator(Cons* cur)
                    : current_(cur)
                {
                }

                const A& operator*() const { return current_->top; }
                iterator& operator++()
                {
                    current_ = current_->rest;
                    return *this;
                }
                bool operator==(const iterator& other) const
                {
                    return this->current_ == other.current_;
                }
                bool operator!=(const iterator& other) const { return !(*this == other); }

            private:
                Cons* current_;
            };

            iterator begin() const { return iterator(elements_); }
            iterator end() const { return iterator(nullptr); }

        private:
            Cons* elements_;
        };

    } // namespace compiler
} // namespace internal
} // namespace v8

#endif // V8_COMPILER_FUNCTIONAL_LIST_H_
